package leetcode.code0581;

import java.util.Stack;

public class Solution1 extends Solution581 {

	@Override
	public int findUnsortedSubarray(int[] nums) {
		int left = Integer.MAX_VALUE; // 左侧第一个逆序的位置
		int right = Integer.MIN_VALUE; //
		Stack<Integer> s1 = new Stack<>(); // 小压大, 大弹小, 找左侧比他大的
		Stack<Integer> s2 = new Stack<>(); // 大压小, 小弹大, 找右侧比他小的
		for (int i = 0; i < nums.length; i++) {
			int cur = nums[i];
			while (!s1.isEmpty() && nums[s1.peek()] <= cur) {// 小压大, 大弹小, 找左侧比他大的
				int index = s1.pop();
				if (!s1.isEmpty()) {// 左边有比index大的,index是交换右端
					right = Math.max(right, index);
				}
			}
			if (left == Integer.MAX_VALUE) {
				// 大压小, 小弹大, 找右侧比他小的, 相等的要压着, 结算的时候需要到最左边
				while (!s2.isEmpty() && nums[s2.peek()] > cur) {
					left = Math.min(left, s2.pop());
				}
			}
			s1.add(i);
			s2.add(i);
		}
		if (left == Integer.MAX_VALUE)
			return 0;
		while (!s1.isEmpty()) {
			int index = s1.pop();
			if (!s1.isEmpty()) {// 左边有比index大的,index是交换右端
				right = Math.max(right, index);
				break;
			}
		}
		return right - left + 1;
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
		so.debug6();
		so.debug8();
		so.debug9();
		so.debug7();
	}

}
